package 图.最短路径;

import 抽象数据类型.IndexMinPQ;
import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-14
 */
public class 最短路径的Dijkstra算法 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 0, 1, 1, 4, 2, 1};
        int[] arr2 = {1, 2, 2, 4, 3, 3, 3, 3};
        double[] weight = {1, 2, 3, 2, 3, 3, -2, 3};
        EdgeWeightedGraph G = new EdgeWeightedGraph(5);
        G.addGraph(arr1, arr2, weight);
        DijkstraSP dijkstraSP = new DijkstraSP(G, 0);
        System.out.println(dijkstraSP.distTo(3));
        for (DirectedEdge edge : dijkstraSP.pathTo(3)) {
            System.out.println(edge);
        }
        System.out.println("lazy----");
        DijkstraSPLazy dijkstraSPLazy = new DijkstraSPLazy(G, 0);
        System.out.println(dijkstraSPLazy.distTo(3));
        for (DirectedEdge edge : dijkstraSPLazy.pathTo(3)) {
            System.out.println(edge);
        }
    }

    public static class DijkstraSP {
        private DirectedEdge[] edgeTo;
        private double[] distTo;
        private IndexMinPQ<Double> pq;

        public DijkstraSP(EdgeWeightedGraph graph, int s) {
            edgeTo = new DirectedEdge[graph.V()];
            distTo = new double[graph.V()];
            pq = new IndexMinPQ<>(graph.V());
            for (int v = 0; v < graph.V(); v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            distTo[s] = 0.0;
            pq.insert(s, 0.0);
            while (!pq.isEmpty()) {
                relax(graph, pq.delMin());
            }
        }

        private void relax(EdgeWeightedGraph graph, int v) {
            for (DirectedEdge e : graph.adj(v)) {
                int w = e.to();
                if (distTo[w] > distTo[v] + e.weight()) {
                    distTo[w] = distTo[v] + e.weight();
                    edgeTo[w] = e;
                    if (pq.contains(w)) {
                        pq.changeKey(w, distTo[w]);
                    } else {
                        pq.insert(w, distTo[w]);
                    }
                }
            }
        }

        public double distTo(int v) {
            return distTo[v];
        }

        public boolean hasPathTo(int v) {
            return distTo[v] < Double.POSITIVE_INFINITY;
        }

        public Iterable<DirectedEdge> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<DirectedEdge> path = new Stack();
            for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
                path.push(e);
            }
            return path;
        }
    }

    //DijkstraSP延时实现
    public static class DijkstraSPLazy {
        private DirectedEdge[] edgeTo;
        private double[] distTo;
        private PriorityQueue<DirectedEdge> pq;
        private Queue<DirectedEdge> mst;


        public DijkstraSPLazy(EdgeWeightedGraph graph, int s) {
            edgeTo = new DirectedEdge[graph.V()];
            distTo = new double[graph.V()];
            pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));
            for (int v = 0; v < graph.V(); v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            mst = new LinkedList<>();
            distTo[s] = 0.0;
            relax(graph, 0);
            while (!pq.isEmpty()) {
                DirectedEdge e = pq.poll();
                int from = e.from();
                int to = e.to();
                mst.offer(e);
                relax(graph, from);
                relax(graph, to);
            }
        }

        private void relax(EdgeWeightedGraph graph, int v) {
            for (DirectedEdge e : graph.adj(v)) {
                int w = e.to();
                if (distTo[w] > distTo[v] + e.weight()) {
                    distTo[w] = distTo[v] + e.weight();
                    edgeTo[w] = e;
                    pq.offer(e);
                }
            }
        }

        public double distTo(int v) {
            return distTo[v];
        }

        public boolean hasPathTo(int v) {
            return distTo[v] < Double.POSITIVE_INFINITY;
        }

        public Iterable<DirectedEdge> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<DirectedEdge> path = new Stack();
            for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
                path.push(e);
            }
            return path;
        }
    }

}
